package _back_tracking

import org.junit.Assert
import org.junit.Test
import kotlin.math.pow

/**
 * 1415. 长度为 n 的开心字符串中字典序第 k 小的字符串
 *
 * 题型：回溯 - 排列
 *
 * https://leetcode.cn/problems/the-k-th-lexicographical-string-of-all-happy-strings-of-length-n/description
 *
 * ```
 * 一个 「开心字符串」定义为：
 *
 * 仅包含小写字母 ['a', 'b', 'c'].
 * 对所有在 1 到 s.length - 1 之间的 i ，满足 s[i] != s[i + 1] （字符串的下标从 1 开始）。
 * 比方说，字符串 "abc"，"ac"，"b" 和 "abcbabcbcb" 都是开心字符串，但是 "aa"，"baa" 和 "ababbc" 都不是开心字符串。
 * 给你两个整数 n 和 k ，你需要将长度为 n 的所有开心字符串按字典序排序。
 * 请你返回排序后的第 k 个开心字符串，如果长度为 n 的开心字符串少于 k 个，那么请你返回 空字符串 。
 *

 * 示例 1：
 * 输入：n = 1, k = 3
 * 输出："c"
 * 解释：列表 ["a", "b", "c"] 包含了所有长度为 1 的开心字符串。按照字典序排序后第三个字符串为 "c" 。
 *
 * 示例 2：
 * 输入：n = 1, k = 4
 * 输出：""
 * 解释：长度为 1 的开心字符串只有 3 个。
 *
 * 示例 3：
 * 输入：n = 3, k = 9
 * 输出："cab"
 * 解释：长度为 3 的开心字符串总共有 12 个 ["aba", "abc", "aca", "acb", "bab", "bac", "bca", "bcb", "cab", "cac", "cba", "cbc"] 。第 9 个字符串为 "cab"
 *
 * 示例 4：
 * 输入：n = 2, k = 7
 * 输出：""
 *
 * 示例 5：
 * 输入：n = 10, k = 100
 * 输出："abacbabacb"
 *
 * 思路：![leetcode_1415.jpg](../../../../images/leetcode_1415.jpg)
 * ```
 *
 */
class leetcode_1415 {
    @Test
    fun test_1() {
        val result = getHappyString(1, 3)
        val expected = "c"
        Assert.assertEquals(expected, result)
    }

    @Test
    fun test_2() {
        val result = getHappyString(1, 4)
        val expected = ""
        Assert.assertEquals(expected, result)
    }

    @Test
    fun test_3() {
        val result = getHappyString(3, 9)
        val expected = "cab"
        Assert.assertEquals(expected, result)
    }

    @Test
    fun test_4() {
        val result = getHappyString(2, 7)
        val expected = ""
        Assert.assertEquals(expected, result)
    }

    @Test
    fun test_5() {
        val result = getHappyString(10, 100)
        val expected = "abacbabacb"
        Assert.assertEquals(expected, result)
    }

    /**
     * 题型：回溯 - 排列
     *
     * 思路：
     * 符合条件字符串的个数：3 * 2^(n-1)，n>0.
     * 如何结算：
     * 方法1 : math 方法。3 * 2.0.pow(n-1).toInt()
     * 方法2 ：位运算。 3 * (1 shl (n-1))
     */
    fun getHappyString(n: Int, k: Int): String {
        // // 长度为 n 的开心字符串的总数量是：3 * 2^(n-1)
//        val maxCount: Int = 3 * (1 shl (n - 1))
        val maxCount: Int = 3 * 2.0.pow(n - 1).toInt()
        if (k > maxCount) {
            return ""
        }
        val array: CharArray = charArrayOf('a', 'b', 'c')
        collect(n, k, array, "")
        return target
    }

    var count: Int = 0
    var target: String = ""
    fun collect(n: Int, k: Int, array: CharArray, path: String) {
        // 1 确定函数参数以及返回值
        // 2 确定终止条件
        // 终止条件
        if (target.length > 0) { // 找到了
            return
        }
        // 收集结果
        if (path.length == n) {
            count++
            if (count == k) {
                target = path
            }
            return
        }
        // 3 确定单层循环的处理逻辑
        for (i in 0 until array.size) {
            // 处理节点
            // TODO:树层不用去重，因为开心字符串相邻的字符不相同。
            // 树枝不用去重。
            if (path.length > 0 && path.get(path.length - 1) == array[i]) {  // s[i] != s[i + 1] （
                continue
            }
            // 递归
            collect(n, k, array, path + array[i])

            // 回溯
            // 剪枝？去重？
        }
    }
}